Міністерство освіти і науки
Вінницький національний технічний університет
Інститут Інформаційних Технологій та Комп’ютерної Інженерії
Кафедра комп’ютерних наук
Лабараторна робота № 9-10
з дисципліни: Дискретна математика.
Тема: Побудова найкоротшого шляху у графі
м.Вінниця 2013 Мета роботи: набути навичок побудови найкоротшого шляху в зваженому графі за допомогою хвильового алгоритму і алгоритму Дейкстри.
Порядок виконання роботи:
Проаналізувати хвильовий алгоритм і алгоритм Дейкстри на конкретному прикладі згідно з індивідуальним завданням.
Розробити схему алгоритму побудови найкоротшого шляху в зваженому графі за хвильовим алгоритмом і алгоритмом Дейкстри.
Розробити програму, яка реалізує дані алгоритму.
Для заданого варіанту привести результати тестування розробленої програми.
Розробити інструкцію користувача.
Оформити звіт і зробити висновки за результатами роботи.
Завдання №14
/
Блок – схема програми що реалізує побудову найкоротшого шляху в зваженому графі за допомогою хвильового алгоритму і алгоритму Дейкстри.
Результати виконання програми. /
Рисунок 2.
Висновок: В ході виконання лабораторної роботи було набуто навичок побудови найкоротшого шляху в зваженому графі за допомогою хвильового алгоритму і алгоритму Дейкстри. , у ході роботи було представлено результати тестування програми яку розроблено на мові С++.
Додаток(лістинг програми, що реалізує побудову найкоротшого шляху в зваженому графі за допомогою хвильового алгоритму і алгоритму Дейкстри).
#include <iostream>
#include <conio.h>
#pragma hdrstop
#pragma argsused
#include <fstream>
#include <algorithm>
#include <vector>
#include <iostream>
using namespace std;
#define VERTEXES 13
int v;
int main(int argc, char* argv[])
{
setlocale(LC_ALL,"");
char arr[13]={'x0','x1', 'x2', 'x3', 'x4', 'x5',
'x6', 'x7', 'x8', 'x9', 'x10','x11','x12'};
int infinity=1000; // Бесконечность
int p= VERTEXES; // Количество вершин в графе
int s,i,j; // Номер исходной вершины
int g; // Номер конечной вершины
cout<<"Введите s: ";cin>>s; // Номер может изменяться от 0 до p-1
cout<<"Введите g: ";cin>>g;
printf(" ");
for(int q=0; q<13; q++)
printf(" x%d",q);
printf("\n");
for(i=0; i<13; i++)
{
printf("x%d",i);
if(i<10)printf(" ");
for(j=0; j<13; j++)
{
printf(" %d ", a[i][j]);
if(j>9)printf(" ");
}
printf("\n");}
int x[VERTEXES]; //Массив, содержащий единицы и нули для каждой вершины,
// x[i]=0 - еще не найден кратчайший путь в i-ю вершину,
// x[i]=1 - кратчайший путь в i-ю вершину уже найден
int t[VERTEXES]; //t[i] - длина кратчайшего пути от вершины s в i
int h[VERTEXES]; //h[i] - вершина, предшествующая i-й вершине
// на кратчайшем пути
// Инициализируем начальные значения массивов
int u; // Счетчик вершин
for (u=0;u<p;u++)
{
t[u]=infinity; //Сначала все кратчайшие пути из s в i
//равны бесконечности
x[u]=0; // и нет кратчайшего пути ни для одной вершины
}
h[s]=0; // s - начало пути, поэтому этой вершине ничего не предшествует
t[s]=0; // Кратчайший путь из s в s равен 0
x[s]=1; // Для вершины s найден кратчайший путь
v=s; // Делаем s текущей вершиной
while(1)
{
// Перебираем все вершины, смежные v, и ищем для них кратчайший путь
for(u=0;u<p;u++)
{
if(a[v][u]==0)continue; // Вершины u и v несмежные
if(x[u]==0 && t[u]>t[v]+a[v][u]) //Если для вершины u еще не
//найден кратчайший путь
// и новый путь в u короче чем
//старый, то
{
t[u]=t[v]+a[v][u]; //запоминаем более короткую длину пути в
//массив t и
h[u]=v; //запоминаем, что v->u часть кратчайшего
//пути из s->u
}
}
// Ищем из всех длин некратчайших путей самый ...
